package os;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author mubei
 * @date 2021/12/8
 * @description
 */
public class OPT {

    // 保存页面和页面出现的位置
    HashSet<Integer> virtualMemory;
    int size;
    int map[][];
    char identifying[];
    int count = 0;

    public OPT(int size) {
        this.size = size;
    }


    private void init(int n){
        map = new int[size][n];
        virtualMemory = new HashSet<>();
        identifying = new char[n];
        Arrays.fill(identifying, '×');
    }

    public  void calc(int[] array) {
        init(array.length);
        for (int i = 0; i < array.length; i++) {
            // 更新虚拟内存
            if(i > 0){
                for (int j = 0; j < size; j++) {
                    map[j][i] = map[j][i - 1];
                }
            }

           if(!virtualMemory.contains(array[i])){
               if(virtualMemory.size()< size){
                  addPage(i,array[i]);
               }else{
                   replacePage(i,array,array[i]);
               }
           }

        }
        print(array.length,array);
    }

    private void addPage(int i,int page){
        virtualMemory.add(page);
        for (int j = 0; j < size; j++) {
            if(map[j][i] == 0){
                map[j][i] = page;
                identifying[i] = '✓';
                count++;
                return;
            }
        }
    }

    private void replacePage(int index,int[] array,int page){

        HashMap<Integer, Integer> map1 = new HashMap<>();
        virtualMemory.forEach((key)->{
            map1.put(key,Integer.MAX_VALUE);
        });

        for (int i = index+1; i < array.length; i++) {
            if(map1.containsKey(array[i]) && map1.get(array[i]) > i){
                map1.put(array[i],i);
            }
        }

        int maxItem = -1;
        int farthestUser = -1;
        for (Integer key : map1.keySet()) {
            if(map1.get(key) > farthestUser){
                maxItem = key;
                farthestUser = map1.get(key);
            }
        }
        virtualMemory.remove(maxItem);
        for (int i = 0; i < size; i++) {
            if(map[i][index] == maxItem){
                map[i][index] = page;
                identifying[index] = '✓';
                break;
            }
        }
        virtualMemory.add(page);
        count ++;
    }

    private void print(int index,int[] arr){
        for (int i = 0; i < index; i++) {
            System.out.print(arr[i]+"\t");
        }
        System.out.println();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < index; j++) {
                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }
        for (int i = 0; i < index; i++) {
            System.out.print(identifying[i]+"\t");
        }
        System.out.println();
        System.out.println("一共替换 "+count+"次");
    }


}
